package sort;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * @Author leecho
 * @Date: 2021/10/20 11:34
 * @Version 1.0
 */

public class RadixSort {
    public static void main(String[] args) {
        SimpleDateFormat df = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        System.out.println(df.format(new Date()));

//        int[] arr = {8,4,5,7,1,3,6,2};

        RadixSort radixSort = new RadixSort();

        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random()*800000);
        }

       radixSort.radixSort(arr);

        System.out.println(df.format(new Date()));
//        System.out.println(Arrays.toString(arr));
    }

    /*
    * 思路
    * - 设定10个桶
    * - 找出原数组最大数字
    * - 分别将个、十、百等上的数字取出，放入桶中
    * - 将桶中的数字取出，赋值给原数组
    *   - 放出的次数，取决于最大数字的最高位
    * */
    public void radixSort(int[] arr){
        int[][] bucket = new int[10][arr.length];
        // 这里还需要定义一个数组来存储每一个桶中存放了多少个数字
        // 这样就可以直到在赋值给原数组时需要遍历的次数
        int[] bucketCount = new int[10];
        
        int max = arr[0];
        for (int i : arr) {
            if (i > max){
                max = i;
            }
        }

        // 技巧： 这里通过将数字转换为字符串的形式，取出最大数字的长度，也就是最高位
        int maxLength = (max + "").length();

        for (int i = 0,n = 1; i < maxLength; i++, n *= 10) {
            for (int j = 0; j < arr.length; j++) {
                int bucketElement = arr[j] / n % 10;
                bucket[bucketElement][bucketCount[bucketElement]] =arr[j];
                bucketCount[bucketElement] ++;
            }

            int index = 0;

            for (int j = 0; j < bucketCount.length; j++) {
                if (bucketCount[j] != 0){
                    for (int k = 0; k < bucketCount[j]; k++) {
                        arr[index] = bucket[j][k];
                        index++;
                    }
                }
                // 每次遍历完都要将存储桶中个数的数组上的数字清零，避免后面如果再次进行桶排序的时候
                // 有可能这次这个桶中并没有存入数字，如果不清零则会进行遍历赋值
                bucketCount[j] = 0;
            }
        }
    }
}
